#include <iostream>
#include <cstdio>
#include <cstring>
#include <unordered_map>
#include <algorithm>
// 如果需要使用std命名空间中的元素，可以添加如下行
using namespace std;

const int MAXSIZE = 1000; // 定义最大页面数
const int NUM = 3; // 定义页框数（物理块数）

typedef struct node {
    int loaded;   // 记录该物理块存储的页面
    int time;     // 记录该物理块最后被访问的时间
} page;

page pages[NUM]; // 定义页框表 （物理块表）
int queue[MAXSIZE];
int quantity;
int currentTime = 0; // 当前时间，用于记录页面最后被访问的时间
unordered_map<int, int> pageMap; // 用于快速查找页面是否在内存中

// 初始化结构函数
void initial() {
    for (int i = 0; i < NUM; i++) {
        pages[i].loaded = -1; // 初始化页面为-1，表示空
        pages[i].time = 0;
    }
    for (int i = 0; i < MAXSIZE; i++)
        queue[i] = -1;
    quantity = 0;
    currentTime = 0;
    pageMap.clear();
}

// 读入页面流
void readData() {
    FILE *fp;
    char fname[20];
    int i;
    cout << "请输入页面流文件名: ";
    cin >> fname;
    if ((fp = fopen(fname, "r")) == NULL) {
        cout << "错误,文件打不开,请检查文件名";
    } else {
        while (!feof(fp)) {
            fscanf(fp, "%d ", &queue[quantity]);
            quantity++;
        }
        fclose(fp); // 读取完毕后关闭文件
    }
    cout << "读入的页面流:";
    for (i = 0; i < quantity; i++) {
        cout << queue[i] << " ";
    }
    cout << endl;
}

// FIFO调度算法
void FIFO() {
    int i, j, p, flag;
    int absence = 0; // 记录缺页次数
    p = 0;
    cout << endl << "----------------------------------------------------" << endl;
    cout << "先进先出调度算法(FIFO)页面调出流: ";
    for (i = 0; i < NUM; i++) { // 前NUM个进入内存的页面
        pages[p].loaded = queue[i];
        cout << pages[p].loaded << " ";
        p = (p + 1) % NUM;
    }
    absence = NUM;
    for (i = NUM; i < quantity; i++) {
        flag = 0;
        for (j = 0; j < NUM; j++) { // 判断当前需求的页面是否在内存
            if (pages[j].loaded == queue[i])
                flag = 1;
        }
        if (flag == 0) {
            cout << pages[p].loaded << " ";
            pages[p].loaded = queue[i];
            p = (p + 1) % NUM;
            absence++;
        }
    }
    cout << endl << "总缺页数:" << absence << endl;
}

// LRU调度算法
void LRU() {
    int absence = 0; // 记录缺页次数
    cout << endl << "----------------------------------------------------" << endl;
    cout << "最近最少使用调度算法(LRU)页面调出流: ";
    for (int i = 0; i < quantity; i++) {
        int requestPage = queue[i];
        if (pageMap.find(requestPage) == pageMap.end()) {
            absence++;
            if (absence > NUM) { // 需要置换页面
                int lruIndex = 0;
                int minTime = pages[0].time;
                for (int j = 1; j < NUM; j++) {
                    if (pages[j].time < minTime) {
                        minTime = pages[j].time;
                        lruIndex = j;
                    }
                }
                cout << pages[lruIndex].loaded << " "; // 置换出的页面
                pages[lruIndex].loaded = requestPage;
                pages[lruIndex].time = ++currentTime;
                pageMap.erase(pages[lruIndex].loaded); // 移除旧页面
                pageMap[requestPage] = lruIndex; // 添加新页面
            } else { // 没有足够的页面框，直接加载新页面
                int pageIndex = absence - 1; // 计算新页面的索引
                pages[pageIndex].loaded = requestPage;
                pages[pageIndex].time = ++currentTime;
                pageMap[requestPage] = pageIndex;
            }
        } else { // 页面已在内存中，更新访问时间
            int index = pageMap[requestPage];
            pages[index].time = ++currentTime;
        }
        cout << requestPage << " ";
    }
    cout << endl << "总缺页数:" << absence << endl;
}

int main() {
    cout << " /**********虚拟存储管理器的页面调度**************/" << endl;
    initial();
    readData();
    // FIFO();
    LRU();
    return 0;
}